{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Non-negative Integers without Consecutive Ones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findIntegers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不含连续1的非负整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>n</code> ，请你统计在&nbsp;<code>[0, n]</code> 范围的非负整数中，有多少个整数的二进制表示中不存在 <strong>连续的 1 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 5\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong> \n",
    "下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：\n",
    "0 : 0\n",
    "1 : 1\n",
    "2 : 10\n",
    "3 : 11\n",
    "4 : 100\n",
    "5 : 101\n",
    "其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2\n",
    "<strong>输出:</strong> 3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [non-negative-integers-without-consecutive-ones](https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [non-negative-integers-without-consecutive-ones](https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findIntegers(self, n: int) -> int:\n",
    "\t\tif n<=1:\n",
    "\t\t\treturn n+1\n",
    "\t\tb=[]\n",
    "\t\twhile n:\n",
    "\t\t\tb.append(n%2)\n",
    "\t\t\tn//=2\n",
    "\t\tn=len(b)\n",
    "\t\tones=[0]*n\n",
    "\t\tzeros=[0]*n\n",
    "\t\tones[0]=zeros[0]=1\n",
    "\t\tres=2\n",
    "\t\tfor i in range(1,n-1):\n",
    "\t\t\tones[i],zeros[i]=zeros[i-1],ones[i-1]+zeros[i-1]\n",
    "\t\t\tres+=ones[i]\n",
    "\t\tfor i in range(n-2,-1,-1):\n",
    "\t\t\tif b[i]==1 and b[i]==b[i+1]:\n",
    "\t\t\t\tbreak\n",
    "\t\tif b[i+1]==0:\n",
    "\t\t\tres+=b[i]+1\n",
    "\t\telse:\n",
    "\t\t\tres+=zeros[i]\n",
    "\t\tfor j in range(i+1,n-1):\n",
    "\t\t\tif b[j]==1:\n",
    "\t\t\t\tres+=zeros[j]\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        b = 32\n",
    "        @lru_cache\n",
    "        # 不需要is_num 因为32位都算了\n",
    "        def f(idx, mask, is_limit, is_num):\n",
    "            if idx == 32:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(idx+1, 0, False, False)\n",
    "            up = (1 if (n&(1<<(31-idx))) else 0) if is_limit else 1\n",
    "            for d in range(0,up+1):\n",
    "                if d == 1:\n",
    "                    if mask == 1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        res += f(idx+1, 1, is_limit and up==d, True)\n",
    "                else:\n",
    "                    res += f(idx+1, 0, is_limit and up==d, True)\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 31\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, 31):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(29, -1, -1):\n",
    "            val = (1 << i)\n",
    "            if n & val:\n",
    "                res += dp[i + 1]\n",
    "                if pre == 1:\n",
    "                    break\n",
    "                pre = 1\n",
    "            else:\n",
    "                pre = 0\n",
    "\n",
    "            if i == 0:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        def fib(length):\n",
    "            if(length==0):\n",
    "                return [1]\n",
    "            if(length==1):\n",
    "                return [1,2]\n",
    "            maxSum = [1,2]\n",
    "            for l in range(2,length+1):\n",
    "                maxSum.append(maxSum[l-2]+maxSum[l-1])\n",
    "            maxSum.sort(reverse=True)\n",
    "            return maxSum\n",
    "        binN = bin(n+1)[2:]\n",
    "        length = len(binN)\n",
    "        thisLenMaxSum = fib(length)\n",
    "        sumNotContinous = thisLenMaxSum[1]\n",
    "        for i in range(1,len(binN)): \n",
    "            if(binN[i]=='1'):\n",
    "                sumNotContinous += thisLenMaxSum[i+1]\n",
    "                if(binN[i-1]=='1'):\n",
    "                    return sumNotContinous\n",
    "        return sumNotContinous\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dp = [[1,1]]\n",
    "        for i in range(1, 32):\n",
    "            self.dp.append([sum(self.dp[-1]), self.dp[-1][0]])\n",
    "\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        pre = False\n",
    "        ans = 0\n",
    "        flag = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            if (((1<<i) & n) or flag) and not pre:\n",
    "                ans += self.dp[i][0]\n",
    "                pre = True\n",
    "            elif ((1<<i) & n) and pre:\n",
    "                flag = 1\n",
    "                pre = False\n",
    "            else:\n",
    "                pre = False\n",
    "\n",
    "        \n",
    "        ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 31\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, 31):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(29, -1, -1):\n",
    "            val = (1 << i)\n",
    "            if n & val:\n",
    "                res += dp[i + 1]\n",
    "                if pre == 1:\n",
    "                    break\n",
    "                pre = 1\n",
    "            else:\n",
    "                pre = 0\n",
    "\n",
    "            if i == 0:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        binary = bin(n)[2:]\n",
    "        N = len(binary)\n",
    "\n",
    "        dp = [1] * (N + 1)\n",
    "        for i in range(2, len(dp)):\n",
    "            dp[i] = sum(dp[:(i - 1)])\n",
    "        ans = sum(dp[:-1])\n",
    "\n",
    "        flag = True\n",
    "        for i in range(1, N):\n",
    "            if binary[i] == '1':\n",
    "                ans += sum(dp[:(N-i)])\n",
    "                if binary[i-1] == '1':\n",
    "                    flag = False\n",
    "                    break\n",
    "        if flag:\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 32\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        for i in range(2, 32):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "\n",
    "        ans, k, pre_bit = 0, 30, 0\n",
    "        while k >= 0:\n",
    "            if (n & (1 << k)) != 0:\n",
    "                ans += dp[k]\n",
    "                if pre_bit == 1:\n",
    "                    ans -= 1\n",
    "                    break\n",
    "                pre_bit = 1\n",
    "            else:\n",
    "                pre_bit = 0\n",
    "            k -= 1\n",
    "\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef findIntegers(self, n: int) -> int:\n",
    "\t\tif n<=1:\n",
    "\t\t\treturn n+1\n",
    "\t\tb=[]\n",
    "\t\twhile n:\n",
    "\t\t\tb.append(n%2)\n",
    "\t\t\tn//=2\n",
    "\t\tn=len(b)\n",
    "\t\tones=[0]*n\n",
    "\t\tzeros=[0]*n\n",
    "\t\tones[0]=zeros[0]=1\n",
    "\t\tres=2\n",
    "\t\tfor i in range(1,n-1):\n",
    "\t\t\tones[i],zeros[i]=zeros[i-1],ones[i-1]+zeros[i-1]\n",
    "\t\t\tres+=ones[i]\n",
    "\t\tfor i in range(n-2,-1,-1):\n",
    "\t\t\tif b[i]==1 and b[i]==b[i+1]:\n",
    "\t\t\t\tbreak\n",
    "\t\tif b[i+1]==0:\n",
    "\t\t\tres+=b[i]+1\n",
    "\t\telse:\n",
    "\t\t\tres+=zeros[i]\n",
    "\t\tfor j in range(i+1,n-1):\n",
    "\t\t\tif b[j]==1:\n",
    "\t\t\t\tres+=zeros[j]\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 31\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, 31):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(29, -1, -1):\n",
    "            val = (1 << i)\n",
    "            if n & val:\n",
    "                res += dp[i + 1]\n",
    "                if pre == 1:\n",
    "                    break\n",
    "                pre = 1\n",
    "            else:\n",
    "                pre = 0\n",
    "\n",
    "            if i == 0:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        num = str(bin(n))[2:]\n",
    "        n = len(num)\n",
    "        f = [[0, 0] for _ in range(n+1)]\n",
    "        ans = 0\n",
    "        f[1][1] = 1\n",
    "        f[1][0] = 1\n",
    "        for i in range(2, n+1):\n",
    "            f[i][0] = f[i-1][0] + f[i-1][1]\n",
    "            f[i][1] = f[i-1][0]\n",
    "        last_bit = 0\n",
    "        for i in range(n):\n",
    "            bit = int(num[i])\n",
    "            if bit == 0:\n",
    "                if i == n-1:\n",
    "                    ans += 1\n",
    "                last_bit = 0\n",
    "                continue\n",
    "            elif last_bit == 1:\n",
    "                if i == n-1:\n",
    "                    ans += f[n-i][0]\n",
    "                else:\n",
    "                    ans += f[n-i][0]\n",
    "                break\n",
    "            else:\n",
    "                if i == n-1:\n",
    "                    ans += f[n-i][0] + 1\n",
    "                else:\n",
    "                    ans += f[n-i][0]\n",
    "                last_bit = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#二进制不含连续1的非负整数的个数，输入: n = 5输出: 5；输入: n = 2输出: 3\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 31\n",
    "        dp[0],dp[1]=1,1\n",
    "        for i in range(2, 31):dp[i] = dp[i - 1] + dp[i - 2]\n",
    "        res,pre=0,0\n",
    "        for i in range(29, -1, -1):\n",
    "            val = (1 << i)\n",
    "            if n & val:\n",
    "                res += dp[i + 1]\n",
    "                if pre == 1:break\n",
    "                pre = 1\n",
    "            else:pre = 0\n",
    "            if i == 0:res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findIntegers(self, n):\n",
    "        bin_str = bin(n)[2:]\n",
    "        length = len(bin_str)\n",
    "        dp = [0] * (length + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        for i in range(2, length):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        res = 0\n",
    "        prev_bit = 0\n",
    "        for i in range(length):\n",
    "            if bin_str[i] == '1':\n",
    "                res += dp[length - i - 1]\n",
    "                if prev_bit == 1:\n",
    "                    res -= 1\n",
    "                    break\n",
    "                prev_bit = 1\n",
    "            else:\n",
    "                prev_bit = 0\n",
    "        return res + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        dp = [0] * 32\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2\n",
    "        for i in range(2, 32):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "            \n",
    "        ans, lastBit = 0, -1\n",
    "        for k in range(30, -1, -1):\n",
    "            bit = (n >> k) & 1\n",
    "            if bit == 1:\n",
    "                ans += dp[k]\n",
    "                if lastBit == 1: return ans\n",
    "            lastBit = bit\n",
    "            \n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        n = bin(n)[2:]\n",
    "        @cache\n",
    "        def dfs(i, flag, is_limit):\n",
    "            if i == len(n):\n",
    "                return 1\n",
    "            res = 0\n",
    "            low = 0\n",
    "            up = int(n[i]) if is_limit else 1\n",
    "            for d in range(low, up+1):\n",
    "                if d == 1 and not flag:\n",
    "                    res += dfs(i+1, True, d == up and is_limit)\n",
    "                elif d == 0:\n",
    "                    res += dfs(i+1, False, d == up and is_limit)\n",
    "            return res\n",
    "        return dfs(0, False, True)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        \n",
    "        bins =list(map(int,list(bin(n)[2:])))  \n",
    "        def dfs(nums,level,limit,pre,mem):\n",
    "            if level==len(nums):\n",
    "                return 1\n",
    "\n",
    "            if not limit and mem[level][pre]:\n",
    "                return mem[level][pre]\n",
    "            maxV = 1 if not limit else nums[level]\n",
    "            count = 0\n",
    "            for i in range(maxV+1):\n",
    "                if i==1 and pre==1:\n",
    "                    continue\n",
    "                count +=dfs(nums,level+1,limit and i==maxV,i,mem)\n",
    "            if not limit:\n",
    "                mem[level][pre]=count\n",
    "            return count\n",
    "        mem = [[None]*2 for _ in range(len(bins))]\n",
    "        return dfs(bins,0,True,0,mem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s=bin(n)[2:]\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,pre,is_limit):\n",
    "            if i==m:\n",
    "                return 1\n",
    "            maxv=int(s[i]) if is_limit else 1\n",
    "            ans=0\n",
    "            for j in range(maxv+1):\n",
    "                if j==pre==1:\n",
    "                    continue\n",
    "                ans+=dfs(i+1,j,is_limit and j==maxv)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = bin(n)[2:]\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, isPrev: bool, isLimit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "\n",
    "            up = int(s[i]) if isLimit else 1\n",
    "            # 填0\n",
    "            res = f(i+1, False, isLimit and up == 0)\n",
    "            # 填1\n",
    "            if not isPrev and up == 1:\n",
    "                res += f(i+1, True, isLimit)\n",
    "            return res \n",
    "        return f(0, False,True)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = str(bin(n))[2:]\n",
    "        @cache\n",
    "        def f(i,pre,is_limit):\n",
    "        #pre 表示i-1位是否为1，如果真则当前位不能为1\n",
    "            if len(s) == i:\n",
    "                return 1\n",
    "            up = int(s[i]) if is_limit else 1\n",
    "            res = f(i+1,False,is_limit and up==0) #填0\n",
    "            if not pre and up==1:\n",
    "                res += f(i+1,True,is_limit) #填1\n",
    "            return res\n",
    "        return f(0,False,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = bin(n)[2:]\n",
    "\n",
    "        @cache\n",
    "        def f(i, prev, is_limit):\n",
    "            if i == len(s):\n",
    "                return 1 \n",
    "            \n",
    "            res = 0 \n",
    "            up = int(s[i]) if is_limit else 1\n",
    "            if (up == 1 and prev != 1):\n",
    "                res += f(i+1, 1, is_limit and 1 == up)\n",
    "            res += f(i+1, 0, is_limit and 0 == up)\n",
    "            return res \n",
    "\n",
    "        return f(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        num = n\n",
    "        s = list(map(int, bin(num).removeprefix('0b')))\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def fun(idx, pre, is_num, is_limit):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "\n",
    "            res = 0\n",
    "            if not is_num: \n",
    "                res += fun(idx + 1, False, False, False)\n",
    "             \n",
    "            lower = 0 if is_num else 1\n",
    "            higher = s[idx] if is_limit else 1\n",
    "            for i in range(lower, higher + 1):\n",
    "                if pre and i == 1: continue\n",
    "                res += fun(idx + 1, i == 1, True, i == higher and is_limit)\n",
    "            return res\n",
    "        \n",
    "        return fun(0, 0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        arr =[int(i) for i in bin(n)[2:]]\n",
    "        n = len(arr)\n",
    "        @cache\n",
    "        def f(indx, limit, pre):\n",
    "            if indx == n:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(0, 2 if not limit else arr[indx]+1):\n",
    "                if pre and i == 1:\n",
    "                    continue\n",
    "                res += f(indx+1, i==arr[indx] and limit, i==1)\n",
    "            return res\n",
    "        return f(0,True,0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==1:\n",
    "                return 1,1\n",
    "            if i==2:\n",
    "                return 2,1\n",
    "            return dfs(i-1)[0]+dfs(i-1)[1],dfs(i-2)[0]+dfs(i-2)[1]\n",
    "        lenth=0\n",
    "        for i in range(31,-1,-1):\n",
    "            if (n>>i)&1==1:\n",
    "                lenth=i+1\n",
    "                break\n",
    "        pre=0\n",
    "        ans=0\n",
    "        for i in range(lenth,0,-1):\n",
    "            cur=(n>>(i-1))&1\n",
    "            if cur==1:\n",
    "                ans+=dfs(i)[0]\n",
    "            if cur==1 and pre==1:\n",
    "                break\n",
    "            pre=cur\n",
    "            if i==1:\n",
    "                ans+=1\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        #抽象解法，宫水三叶大佬的解法\n",
    "        #得带n的位数长度\n",
    "        # def getlen(n):\n",
    "        #     for i in range(31,-1,-1):\n",
    "        #         if (n>>i)&1==1:\n",
    "        #             return i+1\n",
    "        # N=getlen(n)\n",
    "        # f=[[0]*2 for _ in range(N+1)]\n",
    "        # f[1][1],f[1][0]=2,1\n",
    "        # for i in range(2,N+1):\n",
    "        #     f[i][0]=f[i-1][1]\n",
    "        #     f[i][1]=f[i-1][1]+f[i-1][0]\n",
    "        # ans=0\n",
    "        # pre=0\n",
    "        # for i in range(N-1,-1,-1):\n",
    "        #     cur = ((n>>i)&1)\n",
    "        #     if cur==1:\n",
    "        #         ans+=f[i+1][0]\n",
    "        #     if cur==1 and pre==1:\n",
    "        #         break\n",
    "        #     pre=cur\n",
    "        #     if i==0:\n",
    "        #         ans+=1\n",
    "        # return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s=bin(n)[2:]\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,pre,is_limit):\n",
    "            if i==m:\n",
    "                return 1\n",
    "            maxv=int(s[i]) if is_limit else 1\n",
    "            ans=0\n",
    "            for j in range(maxv+1):\n",
    "                if j==pre==1:\n",
    "                    continue\n",
    "                ans+=dfs(i+1,j,is_limit and j==maxv)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        #将n转换为二进制的字符串形式\n",
    "        s = \"{0:b}\".format(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, preis1: bool, is_limit: bool) -> int:     #preis1记录当前位的前一位填的是否为1\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 1       #如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            org = up\n",
    "            up = 0 if preis1 else up    #前一位填的数字不是1时才能有选择的填，否则只能填0，不然就会出现连续的1\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, d, is_limit and d == org)\n",
    "            return res\n",
    "        return f(0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "@lru_cache(None)\n",
    "def cal(upper: int) -> int:\n",
    "    @lru_cache(None)\n",
    "    def dfs(pos: int, pre: int, isLimit: bool) -> int:\n",
    "        \"\"\"当前在第pos位，前一位为pre，isLimit表示是否贴合上界\"\"\"\n",
    "        if pos == 0:\n",
    "            return 1\n",
    "\n",
    "        res = 0\n",
    "        up = nums[pos - 1] if isLimit else 1\n",
    "        for cur in range(up + 1):\n",
    "            if pre == cur == 1:\n",
    "                continue\n",
    "            res += dfs(pos - 1, cur, (isLimit and cur == up))\n",
    "        return res\n",
    "\n",
    "    nums = []\n",
    "    while upper:\n",
    "        div, mod = divmod(upper, 2)\n",
    "        nums.append(mod)\n",
    "        upper = div\n",
    "    return dfs(len(nums), -1, True)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        \"\"\"给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。\"\"\"\n",
    "        return cal(n)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = str(bin(n)[2:])\n",
    "        @cache\n",
    "        def f(i, mask, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            ret = 0\n",
    "            if not is_num:\n",
    "                ret = f(i + 1, mask, False, False)\n",
    "            up = int(s[i]) if is_limit else 1\n",
    "            ret += f(i + 1, 0, is_limit and up == 0, True)\n",
    "            if not mask and up:\n",
    "                ret += f(i + 1, 1, is_limit and up == 1, True)\n",
    "            return ret\n",
    "        return f(0, 0, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = bin(n)[2: ]\n",
    "        # print(s)\n",
    "        @lru_cache \n",
    "        def func(i: int, is_limit: bool, pre: int) -> int: \n",
    "            if i == len(s):\n",
    "                return 1 \n",
    "            \n",
    "            res = 0 \n",
    "            max_d = int(s[i]) if is_limit else 1 \n",
    "            res = func(i+1, is_limit and max_d == 0, 0)\n",
    "\n",
    "            if pre == 0 and max_d == 1:\n",
    "                res += func(i+1, is_limit and max_d == 1, 1)\n",
    "            \n",
    "            return res \n",
    "        \n",
    "        return func(0, True, 0) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = bin(n)[2:]\n",
    "\n",
    "        @cache\n",
    "        def f(i, prev, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return 1 \n",
    "            \n",
    "            res = 0 \n",
    "            if not is_num:\n",
    "                res = f(i+1,0,False,False)\n",
    "            \n",
    "            low = 1 if not is_num else 0\n",
    "            up = int(s[i]) if is_limit else 1\n",
    "            for d in range(low, up+1):\n",
    "                if (d == 1 and prev != 1):\n",
    "                    res += f(i+1, 1, is_limit and d == up, True)\n",
    "                elif d == 0:\n",
    "                    res += f(i+1, 0, is_limit and d == up, True)\n",
    "                else:\n",
    "                    pass \n",
    "            return res \n",
    "\n",
    "        return f(0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = \"\"\n",
    "        while n != 0:\n",
    "            s += str(n & 1)\n",
    "            n >>= 1\n",
    "\n",
    "        s = s[::-1]\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int, pre: bool, isLimit: bool, isNum: bool) -> int:\n",
    "            if u == len(s):\n",
    "                return 1 if isNum else 0\n",
    "            \n",
    "            res = 0\n",
    "            if not isNum:\n",
    "                res += dfs(u + 1, False, False, False)\n",
    "            \n",
    "            up = 1 if not isLimit else ord(s[u]) - ord('0')\n",
    "            down = 0 if isNum else 1\n",
    "            for i in range(down, up + 1):\n",
    "                if i == 1 and pre:\n",
    "                    continue\n",
    "                res += dfs(u + 1, i == 1, i == up and isLimit, True)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(0, False, True, False) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "\n",
    "        s = bin(n)[2:]\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, pre1:bool,is_limit: bool, is_num: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res += f(i + 1,False, False, False)\n",
    "            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "            up = int(s[i]) if is_limit else 1  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                if d==1:\n",
    "                    if not pre1:\n",
    "                        res+=f(i+1,True,is_limit and d==up,True)\n",
    "                else:\n",
    "                    res += f(i + 1, False,is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, False,True, False)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n < 3:\n",
    "            return n + 1\n",
    "\n",
    "        high = 1 << (len(bin(n)) - 3)\n",
    "        if n & (high >> 1):\n",
    "            return self.findIntegers((high >> 1) - 1) + self.findIntegers(high - 1)\n",
    "        else:\n",
    "            return self.findIntegers(n - high) + self.findIntegers(high - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = \"\"\n",
    "        while n != 0:\n",
    "            s += str(n & 1)\n",
    "            n >>= 1\n",
    "\n",
    "        s = s[::-1]\n",
    "\n",
    "        @cache\n",
    "        def dfs(u: int, pre: bool, isLimit: bool, isNum: bool) -> int:\n",
    "            if u == len(s):\n",
    "                return 1 if isNum else 0\n",
    "            \n",
    "            res = 0\n",
    "            if not isNum:\n",
    "                res += dfs(u + 1, False, False, False)\n",
    "            \n",
    "            up = 1 if not isLimit else ord(s[u]) - ord('0')\n",
    "            down = 0 if isNum else 1\n",
    "            for i in range(down, up + 1):\n",
    "                if i == 1 and pre:\n",
    "                    continue\n",
    "                res += dfs(u + 1, i == 1, i == up and isLimit, True)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(0, False, True, False) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def num_to_list(n):\n",
    "    if n < 2:\n",
    "        return [n]\n",
    "    n1,n2 = divmod(n, 2)\n",
    "    return num_to_list(n1) + [n2]\n",
    "@cache\n",
    "def bare_num(n1):\n",
    "    # if n1 = 1, means [1], so can be 1,0\n",
    "    # if n1 = 2, means [1, 0], so can be (1,0),(1),(0)\n",
    "    if n1 == 1:\n",
    "        #print('bare_num', n1, 2)\n",
    "        return 2\n",
    "    if n1 == 2:\n",
    "        #print('bare_num', n1, 3)\n",
    "        return 3\n",
    "    vv = 1 + full_num(n1-1)\n",
    "    #print('bare_num', n1, vv)\n",
    "    return vv\n",
    "@cache\n",
    "def full_num(n1):\n",
    "    # if n1 = 1, means [1], so can be 1,0\n",
    "    # if n1 = 2, means [1, 1], so can be (1,0),(1),(0)\n",
    "    # if n1 = 3, means [1, 1, 1], so can be (1,0,0),(1,0,1),(1,0),(1),(0)\n",
    "    if n1 == 1:\n",
    "        return 2\n",
    "    if n1 == 2:\n",
    "        return 3\n",
    "    num1 = full_num(n1-1)\n",
    "    num2 = full_num(n1-2)\n",
    "    return num1+num2\n",
    "\n",
    "def fix_list(lst):\n",
    "    assert lst[0]\n",
    "    for i in range(1,len(lst)):\n",
    "        if lst[i] and lst[i-1]:\n",
    "            break\n",
    "    else:\n",
    "        return\n",
    "    for j in range(i,len(lst),2):\n",
    "        lst[j] = 0\n",
    "        if j+1 < len(lst):\n",
    "            lst[j+1] = 1\n",
    "\n",
    "def func1(n):\n",
    "    lst = num_to_list(n)\n",
    "\n",
    "    fix_list(lst)\n",
    "\n",
    "    n1 = bare_num(len(lst))-1\n",
    "    for i in range(1,len(lst)):\n",
    "        if not lst[i]:\n",
    "            continue\n",
    "        n1 += bare_num(len(lst)-i)-1\n",
    "    return n1+1\n",
    "\n",
    "class Solution1:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        return func1(n)\n",
    "\n",
    "@cache\n",
    "def find3(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    return find3((n - 1) // 4) + find3(n // 2)\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self,n):\n",
    "        return find3(n)\n",
    "\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        self.n = n\n",
    "        return self.funcFalse(2) + 2\n",
    "\n",
    "    def funcFalse(self, i):\n",
    "        total = 0\n",
    "        while i <= self.n:\n",
    "            d = 0\n",
    "            if i*2+1 <= self.n:\n",
    "                d = 1 + self.funcFalse((i*2+1)*2)\n",
    "            total += 1 + d\n",
    "            i*=2\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = str(bin(n))[2:]\n",
    "        @cache\n",
    "        def f(i, last, is_limit):\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 1\n",
    "            upup = up\n",
    "            if last == 1 and up == 1:\n",
    "                upup -= 1\n",
    "            for j in range(0,upup+1):\n",
    "                print(j)\n",
    "                res += f(i+1, j, is_limit and j == up)\n",
    "            return res\n",
    "        return f(0,0,True)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return n+1 if n < 3 else n\n",
    "        bits = len(bin(n)) - 2\n",
    "        return self.findIntegers((1 << (bits-1))-1) + (self.findIntegers((1<<(bits-2))-1) if (n >> (bits - 2)) & 1 else self.findIntegers(n - (1<<(bits-1))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n < 3:return n + 1\n",
    "        if n==3:return 3\n",
    "     \n",
    "        bits = len(bin(n)) - 2\n",
    "        \n",
    "\n",
    "        t=self.findIntegers((1<<(bits-1))-1) \n",
    "        if (n >> (bits - 2)) & 1:\n",
    "            w= self.findIntegers((1<<(bits-2))-1)\n",
    "        else:\n",
    "            w=self.findIntegers(n - (1<<(bits-1)))\n",
    "\n",
    "\n",
    "\n",
    "        return  t+w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        return [1, 2, 3, 3][n] if n<= 3 else self.findIntegers((1<<((k:= n.bit_length())-1)) -1) + self.findIntegers(n & ((1<<(k-2)) -1) if n < (3<<(k-2)) else ((1<<(k-2)) -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\t@functools.lru_cache(None)\n",
    "\tdef findIntegers(self, n):\n",
    "\t\tif n <= 2:\n",
    "\t\t\treturn n + 1\n",
    "\t\tcnt = 0\n",
    "\t\ttmp = n\n",
    "\t\twhile tmp > 1:\n",
    "\t\t\ttmp >>= 1\n",
    "\t\t\tcnt += 1\n",
    "\t\t#首位仍为1 + 首位为0，按次位为0或1分类\n",
    "\t\tif n >> (cnt - 1) == 2:\n",
    "\t\t\treturn self.findIntegers((1 << cnt) - 1) + self.findIntegers(n - (n >> (cnt - 1) << (cnt - 1)))\n",
    "\t\telse:\n",
    "\t\t\treturn self.findIntegers((1 << cnt) - 1) + self.findIntegers((1 << (cnt - 1)) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return n + 1 if n < 3 else n\n",
    "        bits = len(bin(n)) - 2\n",
    "        return self.findIntegers((1<<(bits-1))-1) + (self.findIntegers((1<<(bits-2))-1) if (n >> (bits - 2)) & 1 else self.findIntegers(n - (1<<(bits-1))))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        return self.findIntegers((1<<((bits:=n.bit_length())-1))-1) + (self.findIntegers((1<<(bits-2))-1) if (n >> (bits - 2)) & 1 else self.findIntegers(n - (1<<(bits-1)))) if n > 3 else (n + 1 if n < 3 else n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n<=2:\n",
    "            return n+1\n",
    "        elif n==3:\n",
    "            return 3\n",
    "        cnt=0\n",
    "        n_copy=n\n",
    "        while n_copy>0:\n",
    "            n_copy//=2\n",
    "            cnt+=1\n",
    "        n1=2**(cnt-1)-1\n",
    "        n2=0\n",
    "        if n&(1<<(cnt-2))==1<<(cnt-2):\n",
    "            n2=2**(cnt-2)-1\n",
    "        else:\n",
    "            n2=n-2**(cnt-1)\n",
    "        return self.findIntegers(n1)+self.findIntegers(n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        x = math.floor((math.log(n, 2)))\n",
    "        m = 2 ** x - 1\n",
    "        y = min(int(2 ** (x - 1)) - 1, n - 2 ** x)\n",
    "        return self.findIntegers(m) + self.findIntegers(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:##############回溯，超时\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        max_len = len(str(bin(n))[2:])\n",
    "        def dfs(max_len, path):\n",
    "            if len(path) >= 2 and path[0] == \"0\": # 0不能开头\n",
    "                return\n",
    "            if max_len == 0: \n",
    "                if path:\n",
    "                    ans.add(path)\n",
    "                return \n",
    "            dfs(max_len - 1, path)\n",
    "            dfs(max_len - 1, path + \"0\") \n",
    "            if not path or path[-1] != \"1\": dfs(max_len - 1, path + \"1\")\n",
    "        ans = set()\n",
    "        dfs(max_len, \"\")\n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "class Solution:##########记忆化搜索\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        print(n)\n",
    "        if n <= 3:\n",
    "            return n + 1 if n < 3 else n\n",
    "        bits = len(bin(n)) - 2\n",
    "        return self.findIntegers((1<<(bits-1))-1) + (self.findIntegers((1<<(bits-2))-1) if (n >> (bits - 2)) & 1 else self.findIntegers(n - (1<<(bits-1))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def __init__(self):\n",
    "        self.dp = [[0,0] for _ in range(50)]\n",
    "        self.dp[1][0] = 1\n",
    "        self.dp[1][1] = 2\n",
    "        for i in range(1, 49):\n",
    "            self.dp[i+1][0] = self.dp[i][1]\n",
    "            self.dp[i+1][1] = self.dp[i][0] + self.dp[i][1]\n",
    "\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        _len = len(bin(n)[2:])\n",
    "        ans = prev = 0\n",
    "        for i in range(_len, -1, -1):\n",
    "            cur = (n>>i) & 1\n",
    "            if cur == 1:\n",
    "                ans += self.dp[i+1][0]\n",
    "            if prev == 1 and cur == 1:\n",
    "                break\n",
    "            prev = cur\n",
    "            if i == 0:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        s = str(bin(n))[2:]\n",
    "        dp = [[-1]*100 for _ in range(100)]\n",
    "        def f(i,pre,is_limit,is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            if not is_limit and is_num and dp[i][pre]>=0: return dp[i][pre]\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i+1,pre,False,False)\n",
    "            up = int(s[i]) if is_limit else 1\n",
    "            down = 0 if is_num else 1\n",
    "            for d in range(down,up+1):\n",
    "                if pre == 1 and d == 1: continue\n",
    "                res += f(i+1,d,is_limit and d==up,True)\n",
    "            if not is_limit and is_num: dp[i][pre] = res\n",
    "            return res\n",
    "        return f(0,0,True,False)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "\n",
    "        if n<=2: \n",
    "            return n+1\n",
    "        if n ==3 :\n",
    "            return 3\n",
    "        return self.findIntegers(n>>1) +self.findIntegers((n-1)>>2)\n",
    "        # count=0\n",
    "        # for i in range(n+1):\n",
    "        #     if i & i << 1 <= 0:\n",
    "        #         count+=1\n",
    "        # return count\n",
    "        # dp=[0]*31\n",
    "        # dp[0]=1\n",
    "        # dp[1]=1\n",
    "        # for i in range(2,31):\n",
    "        #     dp[i]=dp[i-1]+dp[i-2]\n",
    "        # pre=0\n",
    "        # res=0\n",
    "        # for i in range(29,-1,-1):\n",
    "        #     val=(1<<i)\n",
    "\n",
    "        #     if n&val:\n",
    "        #         n-=val\n",
    "        #         res+=dp[i+1]\n",
    "        #         if pre==1:\n",
    "        #             break\n",
    "        #         pre=1\n",
    "        #     else:\n",
    "        #         pre=0\n",
    "            \n",
    "        #     if i==0:\n",
    "        #         res+=1\n",
    "        # return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findIntegers(self, num: int) -> int:\n",
    "        # print(bin(num))\n",
    "\n",
    "        bit = num.bit_length()\n",
    "\n",
    "        ans = 0\n",
    "        last = 0\n",
    "\n",
    "        for i in range(bit - 1, -1, -1):\n",
    "            val = (1 << i)\n",
    "            if num & val:  # 当前首位数字为1\n",
    "                num -= val\n",
    "                ans += self.dfs(i, 0)\n",
    "                if last == 1:\n",
    "                    break\n",
    "                last = 1\n",
    "            else:  # 当前首位数字为0\n",
    "                last = 0\n",
    "\n",
    "            # 处理最后1位的情况\n",
    "            if i == 0:\n",
    "                ans += 1\n",
    "            # print(i, \":\", last, \"->\", ans)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    @functools.lru_cache(None)\n",
    "    def dfs(self, bit: int, last: int = 0):\n",
    "        \"\"\"计算整位的不含连续1的非负整数\"\"\"\n",
    "        if bit == 0:\n",
    "            return 1\n",
    "        if last == 0:\n",
    "            return self.dfs(bit - 1, 0) + self.dfs(bit - 1, 1)\n",
    "        else:  # last == 1\n",
    "            return self.dfs(bit - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n==0:return 1\n",
    "        return self.findIntegers((n-1)>>2) + self.findIntegers(n>>1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n<=2: \n",
    "            return n+1\n",
    "        if n ==3 :\n",
    "            return 3\n",
    "        return self.findIntegers(n>>1) +self.findIntegers((n-1)>>2)\n",
    "        # count=0\n",
    "        # for i in range(n+1):\n",
    "        #     if i & i << 1 <= 0:\n",
    "        #         count+=1\n",
    "        # return count\n",
    "        # dp=[0]*31\n",
    "        # dp[0]=1\n",
    "        # dp[1]=1\n",
    "        # for i in range(2,31):\n",
    "        #     dp[i]=dp[i-1]+dp[i-2]\n",
    "        # pre=0\n",
    "        # res=0\n",
    "        # for i in range(29,-1,-1):\n",
    "        #     val=(1<<i)\n",
    "\n",
    "        #     if n&val:\n",
    "        #         n-=val\n",
    "        #         res+=dp[i+1]\n",
    "        #         if pre==1:\n",
    "        #             break\n",
    "        #         pre=1\n",
    "        #     else:\n",
    "        #         pre=0\n",
    "            \n",
    "        #     if i==0:\n",
    "        #         res+=1\n",
    "        # return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n<=2: \n",
    "            return n+1\n",
    "        if n ==3 :\n",
    "            return 3\n",
    "        return self.findIntegers(n>>1) +self.findIntegers((n-1)>>2)\n",
    "        # count=0\n",
    "        # for i in range(n+1):\n",
    "        #     if i & i << 1 <= 0:\n",
    "        #         count+=1\n",
    "        # return count\n",
    "        # dp=[0]*31\n",
    "        # dp[0]=1\n",
    "        # dp[1]=1\n",
    "        # for i in range(2,31):\n",
    "        #     dp[i]=dp[i-1]+dp[i-2]\n",
    "        # pre=0\n",
    "        # res=0\n",
    "        # for i in range(29,-1,-1):\n",
    "        #     val=(1<<i)\n",
    "\n",
    "        #     if n&val:\n",
    "        #         n-=val\n",
    "        #         res+=dp[i+1]\n",
    "        #         if pre==1:\n",
    "        #             break\n",
    "        #         pre=1\n",
    "        #     else:\n",
    "        #         pre=0\n",
    "            \n",
    "        #     if i==0:\n",
    "        #         res+=1\n",
    "        # return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        # count=0\n",
    "        # for i in range(n+1):\n",
    "        #     if i & i << 1 <= 0:\n",
    "        #         count+=1\n",
    "        # return count\n",
    "        # dp=[0]*31\n",
    "        # dp[0]=1\n",
    "        # dp[1]=1\n",
    "        # for i in range(2,31):\n",
    "        #     dp[i]=dp[i-1]+dp[i-2]\n",
    "        # pre=0\n",
    "        # res=0\n",
    "        # for i in range(29,-1,-1):\n",
    "        #     val=(1<<i)\n",
    "\n",
    "        #     if n&val:\n",
    "        #         n-=val\n",
    "        #         res+=dp[i+1]\n",
    "        #         if pre==1:\n",
    "        #             break\n",
    "        #         pre=1\n",
    "        #     else:\n",
    "        #         pre=0\n",
    "            \n",
    "        #     if i==0:\n",
    "        #         res+=1\n",
    "        # return res\n",
    "        if n<=2: \n",
    "            return n+1\n",
    "        if n ==3 :\n",
    "            return 3\n",
    "        return self.findIntegers(n>>1) +self.findIntegers((n-1)>>2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        答案类型：\n",
    "        末尾是1：XXXXXXX01\n",
    "        末尾是0：XXXXXXXX0\n",
    "        \"\"\"\n",
    "        if n==0:return 1\n",
    "        return self.findIntegers((n-1)>>2) + self.findIntegers(n>>1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n==0:return 1\n",
    "        return self.findIntegers((n-1)>>2) + self.findIntegers(n>>1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def findIntegers(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 1\n",
    "        return self.findIntegers((n - 1) >> 2) + self.findIntegers(n >> 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
